1293. Shortest Path in a Grid with Obstacles Elimination

https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

題目解釋

你會得到一個m*n大小的表格，表格填滿了0和1，0和1分別代表通道和障礙物

你還會得到一個數字k，k代表你你可以排除掉幾個障礙物

請回傳從最左上角(0,0)到最右下角(m-1, n-1)最短須走幾步，如果無法到達則回傳-1

example

解法

這題想不到明確的解法，所以直接找其他人的答案，其中一篇解釋得很清楚

所以今天就大致翻譯他給的key process

• 每一步都要確認是否到達終點，如果不是就繼續搜尋
• 每一格的下一步都有4個方向，要確認每一步是否可行(是否到達邊界、是否還有多餘的k能去掉障礙物)
• 重複這個步驟直到到達終點，若是k耗盡且未抵達終點則回傳-1

程式碼

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        
        if k >= m + n - 2: return m + n - 2
        # 如果 k > 最短路徑的步數，就能直直的走過去
        
        q = deque([(0, 0, 0, k)]) # (row, column)目前位置, 累積步數, 剩餘的k
        visted = set() # 紀錄走過的路，避免走回頭路
        
        direct = [(0,1), (1,0), (0,-1), (-1,0)]
        # 四個方向
        
        while q:
            
            row, col, step, k = q.popleft()
            
            if row == m-1 and col == n-1:
            # 到達終點
                return step
            
            for i, j in direct:
                
                if 0 <= row + i and row + i < m and 0 <= col + j and col + j < n and (row + i, col + j, k) not in visted:
                # 確認是否為邊界，是否為走過的格子
                    
                    if grid[row + i][col + j] == 1 and k > 0: #遇到障礙物
                        q.append((row + i, col + j, step + 1, k - 1))
                        visted.add((row + i, col + j, k))
                    if grid[row + i][col + j] == 0: #有通道
                        q.append((row + i, col + j, step + 1, k))
                        visted.add((row + i, col + j, k))
        return -1